package com.example.ac36;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @description
 * @auther lijiewei
 * @date 2022/1/19 17:01
 */

public class AC {

    private AcNode root = new AcNode('/');

    /**
     * 构建失败指针
     * @return
     * @author lijiewei
     * @date   2022/1/19 17:27
     */
    public void buildFialurePointer() {
        Queue<AcNode> queue = new LinkedList<>();
        //根节点为null
        root.fail = null;
        queue.add(root);
        while (!queue.isEmpty()) {
            //获取并移除此列表的头
            AcNode p = queue.remove();
            for (int i = 0; i < 26; i++) {
                //获取子节点
                AcNode pc = p.children[i];
                if (pc == null) {
                    continue;
                }
                //根节点的子节点的失败指针都指向根节点
                if (p == root) {
                    pc.fail = root;
                } else {
                    AcNode q = p.fail;
                    while (q != null) {
                        //获取 q 子集中和 pc 相等的 节点
                        AcNode qc = q.children[pc.data-'a'];
                        //存在相等的子节点
                        if (qc != null) {
                            pc.fail = qc;
                            break;
                        }
                        //不存在相等的子节点，继续找可匹配后缀
                        q = q.fail;
                    }
                    if (q == null) {
                        //没有可匹配后缀子串
                        pc.fail = root;
                    }
                }
                //将 pc 节点放入队列，继续往后推导 pc 的子节点
                queue.add(pc);
            }
        }
    }

    /**
     * 匹配字符串
     * @param text 主串
     * @return
     * @author lijiewei
     * @date   2022/1/20 9:57
     */
    public void match(char[] text) {
        int n = text.length;
        AcNode p = root;
        for (int i = 0; i < n; i++) {
            int index = text[i]-'a';
            //不是根节点，且子节点不对应
            while (p.children[index] == null && p != root) {
                //失败指针找可匹配后缀
                p = p.fail;
            }
            p = p.children[index];
            //没有可匹配的，从root重新匹配
            if (p == null) {
                //下次查找又从根节点开始
                p = root;
            }
            AcNode tmp = p;
            //打印出可以匹配的模式串
            while (tmp != root) {
                if (tmp.isEndingChar == true) {
                    int pos = i-tmp.length+1;
                    System.out.println("匹配起始下标：" + pos + ";长度：" + tmp.length);
                }
                tmp = tmp.fail;
            }
        }
    }

    public AcNode getRoot() {
        return root;
    }

    public void setRoot(AcNode root) {
        this.root = root;
    }
}
